package bean.linklist;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 测试链表删除倒数第N个节点
 */
public class TestLinkList {

    @Test
    public void testLink() {
        Node node1 = new Node();
        node1.setValue(1);
        Node node2 = new Node();
        node2.setValue(2);
        Node node3 = new Node();
        node3.setValue(3);
        Node node4 = new Node();
        node4.setValue(4);
        Node node5 = new Node();
        node5.setValue(5);
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;

        removeNthFromEnd(node1, 1);
        Node n = node1;
        while (n != null) {
            System.out.println("node-value:" + n.getValue());
            n = n.next;
        }
    }

    public Node removeNthFromEnd(Node head, int n) {
        // 双指针，先让一个指针走N步，然后两个指针同时走直到先走的指针不能再走（next为空）此时晚走的指针距离链表结尾为N个节点距离，删除这个指针指向的节点即可
        Node temp = head;
        Node p = head;
        Node q = head;

        while (n > 0) {
            p = p.next;
            n--;
        }
        while (p != null && p.next != null) {
            p = p.next;
            q = q.next;
        }
        if (q != null && q.next != null) {
            q.next = q.next.next;
        }
        return temp;

        // 网络的解决方案：创建了一个节点，充当head节点，防止只有一个节点时报错
//        Node pre = new Node();
//        pre.setValue(0);
//        pre.next = head;
//        Node start = pre, end = pre;
//        while(n != 0) {
//            start = start.next;
//            n--;
//        }
//        while(start.next != null) {
//            start = start.next;
//            end = end.next;
//        }
//        end.next = end.next.next;
//        return pre.next;

    }

    @Test
    public void main1() {
        Integer i1 = new Integer(100);
        Integer i2 = new Integer(100);
        System.out.println(i1 == i2);
        System.out.println(i1.equals(i2));
        // 对于基本数据类型的包装类型，equal方法重写了比较的逻辑，equal方法比较的是基本数据类型的值
    }

    @Test
    public void testNums() {
        int n[] = {1, 3, 5, 6};
        int target = 7;
        int result = searchInsert(n, target);
        System.out.println("result:" + result);
    }

    public int searchInsert(int[] nums, int target) {
//        int pos = 0;
//        for (int i = 0; i < nums.length; i++) {
//            if (target == nums[i]) {
//                pos = i;
//                return pos;
//            }
//            if (target < nums[i]) {
//                pos = i;
//                break;
//            }
//            if(target>nums[i]){//target 比任何数大，插入到最后
//                ++pos;
//            }
//        }
//        int newNums[] = new int[nums.length + 1];
//        for (int i = 0; i < newNums.length; i++) {
//            if (i < pos) {
//                newNums[i] = nums[i];
//            } else if (i == pos) {
//                newNums[i] = target;// i位置插入了新数字
//            } else {
//                newNums[i] = nums[i-1];//新数组i+1,旧数据依然取的原来的位置的
//            }
//        }
//        for (int newNum : newNums) {
//            System.out.println("newItem-" + newNum);
//        }
//        return pos;

        //二分法查找
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;//如果不存在，left的位置就是插入下标

    }

    int[][] arr = {
            {3, 4},
            {1, 3},
            {7, 8},
            {4, 6}
    };

    @Test
    public void testArray() {
//        merge(arr);
        merge1(arr);
    }

    /**
     * 合并N个区间的问题
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];//对二维数组按照第一个值排序
            }
        });
        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];
            for (int j = 0; j < interval.length; j++) {
                System.out.println("interval-" + interval[j]);
            }
        }
//            Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];//创建一个新的二维数组保存合并后的
        int idx = -1;
        for (int[] interval : intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {//res[idx][1])表示合并后的结果区间的末尾
                res[++idx] = interval;//第一次idx == -1 直接复制，拍过序第一个数组就是最小的
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);//比较区间的末尾值，替换结果区间末尾值
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }

    /**
     * 合并区间操作（二维数组中，元素为长度是2的一维数组）
     * @param intervals
     * @return
     */
    public int[][] merge1(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];// 对二维数组按照一维数组的第一个元素排序
            }
        });
        int result[][] = new int[intervals.length][2];
        int index = -1;
        for (int[] interval : intervals) {// 遍历二维数组，把二维数组中的数组整体作为一个个的元素
            if (index == -1 || interval[0] > result[index][1]) {//如果是第一个，或者当前区间的起始位置 > 结果区间的终止位置，则直接赋值
                result[++index] = interval;//赋值一维数组到下一个值
            }else{//直接将当前区间合并到结果区间的最后
                result[index][1] = Math.max(result[index][1],interval[1]);// 比较结果区间和当前区间的末尾值大小
            }
        }
        return Arrays.copyOf(result,index+1);//这里填写的是数组的长度，不是下标，index是下标
    }

}
